package Bondarenko.algorithm.calc;

//Reverse Polish Notation


import java.util.LinkedList;
public class PPN {
  static boolean isDelim(char c) {
  return c == ' ';
  }
  static boolean isOperator(char c) {
  return c == '+' || c == '-' || c == '*' || c == '/';
  }
  static int priority(char op) {
    switch (op) {
    case '+':
    case '-':
      return 1;
    case '*':
    case '/':
    
      return 2;
    default:
      return -1;
    }
  }
  static void processOperator(LinkedList<Integer> st, char op) {
    int r = st.removeLast();
    int l = st.removeLast();
    switch (op) {
    case '+':
      st.add(l + r);
      break;
    case '-':
      st.add(l - r);
      break;
    case '*':
      st.add(l * r);
      break;
    case '/':
      st.add(l / r);
      break;
    }
  }
    public static int eval(String s) {
    LinkedList<Integer> st = new LinkedList<Integer>();
    LinkedList<Character> op = new LinkedList<Character>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (isDelim(c))
        continue;
       else if (isOperator(c)) {
        while (!op.isEmpty() && priority(op.getLast()) >= priority(c))
        processOperator(st, op.removeLast());
        op.add(c);      
      } else {
        String operand = "";
        while (i < s.length() && Character.isDigit(s.charAt(i)))
        operand += s.charAt(i++);        
        --i;        
        st.add(Integer.parseInt(operand));
      }
    }    
    while (!op.isEmpty())
      processOperator(st, op.removeLast());
    return st.get(0);
  }
}